COMMENT ⊗   VALID 00006 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.BEGIN "PREF"
C00015 00003	This text is %6not%* meant to be a programming manual for LISP.
C00030 00004	The text is large and covers much more than is  recommended for a one-semester
C00039 00005	.NEXT PAGE
C00040 00006	.NEXT PAGE
C00041 ENDMK
C⊗;
.BEGIN "PREF"
.PREF
.EP;
"... it is important not to lose sight of the fact that there is a difference
between training and education.  If computer science is a fundamental discipline,
then university education in this field should emphasize enduring fundamental
principles rather than transient current technology."
.PT24;
.BEGIN TURN ON"→";
→Peter Wegner, %3Three Computer Cultures%*#[Weg#70]########
.END
.PT24
.PT24
.PT2
.FP
This text is nominally about LISP and data structures. However, in the process
it 
covers much broader areas of computer science.
The author has long 
felt that the  beginning student of computer science has been getting a distorted 
and disjointed picture of the field. In some ways this confusion is natural; the
field has been growing at such a  rapid rate that few  are prepared
to be judged experts in all areas of the discipline.  The current alternative
seems to be to give a few introductory courses in programming and machine organization
followed by relatively specialized courses in more technical  areas. 
The difficulty with this approach is that much of the technical material
never gets related. The student's perspective and motivation suffer in the
process. This book uses LISP as a means for relating topics which normally
get treated in several  separate  courses. The point is not that we %6can%*
do this in LISP, but rather that it is %6natural%* to do it in LISP.
The high-level notation for algorithms is beneficial in explaining and understanding
complex algorithms.
The use of abstract data structures and abstract LISP programs shows the
 intent of structured programming and step-wise refinement. Much
of the current work in mathematical theories of computation is based on LISP-like
languages. Thus LISP is a formalism for describing algorithms, for writing programs, and
for proving properties of algorithms.
We use data structures as the main thread in our discussions because 
a proper appreciation of data structures as abstract objects is a necessary
prerequisite to an understanding of modern computer science.

The importance of abstraction obviously goes much farther than its
appearance in LISP. Abstraction has often been used in other
disciplines as a means for controlling complexity. 
In mathematics, we frequently are able to gain new insights by recasting
a particularly intransigent problem in a more general setting.
Similarly, the intent of an algorithm
expressed in a high-level language like Fortran or PL/1 
is more readily apparent than its machine-language equivalent.
These are both examples of the use of abstraction. Our use of abstraction
will impinge on both the mathematical and the programming aspects.
Initially, we will talk about data structures as abstract objects
just as the mathematician takes  the natural numbers as abstract
entities. We will attempt to categorize properties common to
data structures and introduce notation for describing functions
defined on these abstractions. At this level of discussion
we are thinking of our LISP-like language primarily as a notational
convenience rather than a computational device.
However, after a certain  familiarity
has been established it is important to look at our work from the
viewpoint of computer science. Here we must think of the computational
aspects of our notation. We must be concerned with the representational
problems: implementation on realistic machines, and  efficiency
of algorithms and data structures. However, it cannot be over-emphasized
that our need for understanding is best served at the higher level
of abstraction; the advantage of a high-level language is notational rather
than computational. That is, it allows us to think  and represent our
algorithms in mathematical terms rather than in terms of the machine.
It is after a clear understanding of the
problem is attained that we should begin thinking about representation.


We can exploit the analogy with traditional mathematics a bit further.
When we write %3sqrt(x)%* in Fortran, for example, we are
initially only concerned with %3sqrt%* as a mathematical function
defined such that %3x#=#sqrt(x)*sqrt(x)%*. We are not interested
in the specific algorithm used to approximate the function
intended in the notation. Indeed, thought of as a mathematical notation,
it doesn't matter how %3sqrt%* is computed. We might wish to prove
some  properties of the algorithm which we are encoding.
If so, we would only use the mathematical properties of the idealized
square root function. Only later, after we had convinced ourselves
of the correct encoding of our intention in the Fortran program,
would we worry about the  computational aspects of the Fortran
implementation %3sqrt%*. The typical user will never
proceed deeper into the representation than this; only if
his computation is lethargic due to inefficiencies, or inaccurate due
to uncooperative approximations, will he look at the actual 
implementation of %3sqrt%*.


Just as it is unnecessary to learn machine language to study numerical
algorithms, it is also unnecessary to learn machine language to understand
non-numerical or data structure processes.  
We make a  distinction  between data
structures and storage structures. Data structures   are 
abstractions, independent
of %6how%* they are implemented on a machine.  Data structures are representations
of information chosen to exhibit certain ordering and accessibility relationships
between data items.  Storage structures are particular implementations
of the abstract ideas.
Certainly  we cannot ignore
storage structures when we are deciding upon the data structures which
will encode the algorithm, but the interesting aspects of the representation of
information can be discussed at the level of data structures with no loss
of generality.  The mapping of data structures to storage structures is
usually quite machine dependent 
and 
  we are more interested in ideas than coding tricks.
We will see that it is possible,
and most beneficial, to structure our programs such that there is a very
clean interface between the abstract algorithm and the chosen representation.
That is, there will be a set of representation-manipulating programs to test,
select or construct elements of the domain; and there will be a program
encoding the algorithm. Changes of representations only require  changes
to the programs which access the representation, not to the basic program.


One important insight which should be cultivated in this process
is the distinction between the concepts of function and algorithm.
The idea of function is mathematical and is independent of any notion
of computation; the meaning of "algorithm" is computational, the
effect of an algorithm being to compute a function. Thus there are
typically many algorithms which will compute a specific function.

This text is %6not%* meant to be a programming manual for LISP.
A certain amount of time is spent giving insights into techniques for
writing LISP functions.  
There are two reasons for this. First, the style
of LISP programming is quite different from that of "normal" programming.
LISP was one of the first languages to exploit the virtues of recursive
programming and explore the power of procedure-valued variables.
Second, we will spend a great deal of time discussing
various levels of implementation of the language. LISP is an excellent
medium for introducing standard techniques 
in data structure manipulation. Techniques for
implementation of recursion, implementation of complex data
structures,  storage management,
and symbol table manipulation are easily motivated in the context
of language implementation. Many of these standard techniques first arose
in the implementation
of LISP. But it is pointless to attempt a discussion
of implementation unless the reader has a thorough grasp of the
language.

Granting the efficacy of our endeavor in abstraction, why study LISP?
LISP is at least fifteen years old and
many  new languages have been proposed.
The difficulty is that the appropriate combination of these features is not
present in any other language. LISP unifies and rationalizes many divergent
formulations  of language constructs.
One might surmise that a new language, profiting from LISP's experience,
would make a better pedagogical tool.
A strong successor has not arrived, and
toy languages are suspect for several reasons. The student may suspect
  that he is a subject in a not too clever
experiment being performed upon him by his instructor. 
Having a backlog of fifteen years of
experience and example programs should do much to alleviate this discomfort.
The development of LISP also shows many of the mistakes 
that the original implementors and designers made.
We will point out the flaws and pitfalls awaiting the unwary language designer.


We claim
the more interesting aspects of LISP for students of computer science lie
not in its features as a programming language, but in what it can show
about the %6structure%* of computer science.
There is a
rapidly expanding body of knowledge unique to computer science, neither
mathematical nor engineering per se.  Much of this area is presented most
clearly by studying LISP.

Again there are two ways to look at a high level language: as a mathematical
formalism, and as a programming language.
LISP is a better formalism than most of its mathematical rivals
because there is sufficient organizational
complexity present in LISP so as to make its implementation a realistic 
computer science task and not just
an interesting mathematical curiosity.
Much of the power of LISP lies in its simplicity.
The data structures are rich enough  to easily
describe sophisticated algorithms but not so rich as to become obfuscatory.
Most every aspect of the implementation
of LISP and its translators has immediate implications to the implementation of 
other languages and to the design of programming languages in
general.

We will describe language translators (interpreters and compilers) as 
LISP functions.  The structure of these translators when exposed as 
LISP functions aids immensely in understanding the essential
character of such translators.
This is partly due to the simplicity of the language, but perhaps more
due to our ability to go right to the essential translating algorithm 
without becoming
bogged down in details of syntax.

LISP has very important implications in the field of programming language
semantics, and  is the dominant language in the closely related study of
provability of properties of programs.
The idea of proving properties of programs has been around for a very
long time. Goldstein and von Neumann were aware of the practical benefits
of such endeavors. J. McCarthy's work in LISP and the Theory of Computation
sought to establish formalisms and rules of inference for  reasoning
about programs.
However, the  working programmers recognized debugging as the
only tool with which to generate a "correct" program, though  clearly
the non-occurrence of bugs is no guarantee of correctness.
Until
very recently techniques for establishing correctness of practical
programs simply did not exist.

A recent set of events is beginning to change this.
.PT24
.NL
%21.%* Programs are becoming so large and complex that, even though
we write in a high-level language, our intuitions are not sufficient
to sustain us when we try to find bugs. We are literally being forced
to look beyond debugging.
.NL
%22.%* The formalisms are maturing. We know a lot more about how
to write "structured programs"; we know how to design languages
whose constructs are more amenable to proof techniques.
And most importantly, the tools we need for expressing properties of 
programs are finally being developed.
.NL
%23.%* The development of on-line techniques. The on-line system,
with its
sophisticated display editors, debuggers and file handlers,
is the
only reason that the traditional means of construction and
modification of complex programs and systems has been able to survive 
this long. The interactive experience can now be adapted to 
program verifiers  and synthesizers.
.PT24

This  view of the programming  process blends well with the LISP philosophy.
We  will show that the most natural way to write LISP programs
is "structured" in the best sense of the word, being  clean in
control structure, concise by not attempting to do too much,
and independent of a particular data representation.

Many of the existing techniques for establishing correctness originated
in McCarthy's investigations of LISP; and some  very recent work
on mathematical models for programming languages is  easily motivated from
a discussion of LISP. 

LISP is the starting point for those interested in Artificial Intelligence.
It is no longer the "research" language, but has become the "systems"
language for A.I. Today's research languages are  built on LISP,
using LISP as a machine language.

Finally there are certain properties of LISP-like languages which
make them the natural candidate for  interactive program specification.
In the chapter on implications of LISP we will characterize "LISP-like"
and show how interactive methods can be developed.


This text is primarily designed for undergraduates and therefore
an attempt is made to make it self-contained. 
There are basically five areas in which to partition the topics:
the mechanics of the language, the evaluation of expressions in LISP,
the static structure of LISP, the dynamic structure of LISP, and the
efficient representation of data structures and algorithms.
Each area
builds on the previous. Taken as a group these topics introduce 
much of what is interesting computer science.

The first area develops  the programming philosophy of LISP: the use
of data structures in programming; the language primitives,   recursion, and
other control structures.  The second area, involving a careful study of the
meaning of evaluation in LISP, gives insights into other languages and to the
general question of implementation. The next two areas are involved with
implementation. The section on static structure deals with the basic 
organization of memory for a LISP machine#--#be it hardware or simulated
in software. The dynamics of LISP  discusses the primitive control structures
necessary for implementation of the LISP control structures  and procedure
calls. LISP compilers are discussed here.
The final section relates our discussion of LISP and its implementation
to the more traditional material of a  data structures course. We discuss the
problems of efficient representation of data structures. By this point
the student should have a better understanding of the uses of data structures
and should be motivated to  examine these issues with a better understanding.

A large collection of problems has been included. The reader is urged to do as
many as possible.  The problems are mostly non-trivial; they attempt to be
realistic, introducing some new information which the readers should be
able to discover themselves. 
There are also a few rather substantial projects.  At least one should be attempted.
There is a significant difference between being able to program small problems
and being able to handle large projects. Small programming projects can be 
accomplished in spite of any admonitions about "good programming style".
A large project   is an effective demonstration of the need
for elegant programming techniques.
The text is large and covers much more than is  recommended for a one-semester
course. 
A typical  one semester course on data structures covers:
.BOXA
.BEGIN INDENT 10,10;NOFILL;
Chapter 1: all
.PT2
Chapter 2: without 2.4, 2.5, and 2.10.
.PT2
Chapter 3: without the mathematical aspects of 3.13
.PT2
Chapter 4: without 4.7, 4.8, and the mathematical aspects of 4.11
.PT2
Chapter 5: without 5.8, 5.19, and 5.20
.PT2
Chapter 6: without 6.8,  and 6.12 through 6.20
.PT2
Chapter 7: without 7.5, 7.6,  and 7.10 through 7.14
.PT2
Chapter 8 is also optional.
.END
.BOXB

If a  good interactive  LISP implementation is available, then
the pace can be quickened and the projects enlarged.  
However, if only a  poor or mediocre 
implementation is  accessible, then the course time is better spent without
%6any%1  actual programming, or the course should be augmented to
include an implementation laboratory.
LISP is an interactive language; attempts
at other modes of operation do a disservice to both the language and
the user.


Finally a note on the structure of the text. 
The emphasis  flows from the abstract to the specific, 
beginning
with a description of the domain of LISP functions
and the operations defined over that domain, and  moves to a discussion
of the details of efficient implementation of LISP-like languages.
The practical-minded programmer might be put off by the "irrelevant"
theory and the theoretical-minded mathematician might be put off
by the "irrelevant" details of implementation. If you lie somewhere  between
these two extremes, then welcome.

.END "PREF"
.cent(Acknowledgements)
.fp
This book began informally at UCLA in 1970 as an alternative to the data
structures course. Any book which takes eight years to complete must 
have a list of acknowledgements.
Between  the 1970 manuscript and the  present
version stretches an incredible list of revisions and rewritings.
That task was made possible only by the document
preparation system at the Stanford Artificial Intelligence Laboratory.
The Artificial Intelligence community is still the superior
developer of computer related tools. 

The final shape of this book has been guided by many sources, but particularly
I would like to mention  Michael Burke and  the San Jose State Mathematics
Department, who
allowed me to use my manuscript in their data structures course.
To Ruth Davis who read and re-read the enumerable  versions of paragraphs,
sections, and chapters, trying to make sense  out of the author
and his material; her reward: to copy-edit the manuscript. Ruth's aid 
 has been both technical and personal; without her there would be no
"Anatomy of LISP."
To Nancy Meller of the UCLA Computer Science Department for typing the
orginal LISP notes.
To Les Earnest of the Stanford A.I. Labs for aid beyond the call of duty.
To Paulette for trying to understand. 
To Richard Manuck of the Stanford Computer Science  Library, a most excellent
librarian with an exceptional library.
To John McCarthy for  the insight  which led to LISP, and
 for establishing an environment at Stanford which
is  staffed so admirably and supplied with so many talented people.
To E, PUB, and the XGP, for existing.
To Dick Dolan and the staff of the H. P. Journal, who  both tolerated and
 sympathized with my attempts to transform  the computer generated text into
something which could be typeset.

Particular mention must go to  Guy Steele
and Gianfranco Prini. Guy  reviewed a much inferior
version of this text. His insights, comments, and criticisms 
were  invaluable. With comments like: "that's not a compromise, it's a
bloody surrender!", the text was bound to improve. Gianfranco, was more
fortunate; he reviewed the results of Guy's scoldings. 
.turn on "#";
.next page
Many other people have had significant influence on the text. I feel fortunate
to  be able to acknowledge these individuals: 
Bruce Anderson,
Bob Boyer,
Michael Clancy,
Bob Doran,
Daniel Friedman,
Richard Gabriel,
Michael Gordon,
Patrick Greussay, 
Anthony Hearn,
Freidrich von#Henke,
Forrest Howard,
Bill McKeeman, 
Peter Milne, 
J#S. Moore,
Jorge Morales,
Charles Prenner,
Steve Russell, 
Hanan Samet,
Vic Scheinman,
Herbert Stoyan, 
Dennis Ting,
and Steve Ward. 
I apologize to any individuals I neglected to mention; I
must surely have forgotten someone.

Similarly there are topics  related to LISP which I have neglected.
The whole area of Artificial Intelligence applications has been
slighted, but
for every author there must come a time when you have to say "Enough!"
I've been saying that for several years. It is particularly difficult
to  cease when dealing with a topic as  dynamic as LISP. Many sections
only hint at deeper problems, and surely some errors persist; but "Enough!"

As always, it is the author's responsibility for the final shape of a
document; the substantial and textual errors, errors of omission and commission
are all mine. Each of the reviewers objected strongly to one or more facets
of this book; to some, it was too theoretical; for some, too  practical.
I must have done something right.

.begin turn on "→";
→%3John Allen%1
.end
.NEXT PAGE;
.GROUP SKIP 10;
.begin TABIT3(20,30,40);
.SELECT 3;
\To my parents, John & Esther Allen
\\To my friend and wife, Ruth E. Davis
\\\To my sons, Christopher & Geoffrey 
.end
.NEXT PAGE
.once CENTER
%2Production Note%1

.fp
The creation, revision, and styling of this document were perfomed using
 the Document Production System at Stanford's Artificial Intelligence
Laboratory; the  pages of this book are  computer generated.
Since higher quality type was desired and such technology was not yet
readily available, an attempt was made to generate
more traditional typeset output. That attempt finally failed.
Thus the production of this book is a uniquely twentieth century experience:
a result of a ninteenth century resistance  and a twenty-first century 
anticipation.